package com.example.maze.generator;

import com.example.maze.model.Cell;
import com.example.maze.model.Coordinate;
import com.example.maze.model.Maze;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.Random;

/**
 * 使用递归分割法生成迷宫
 * 
 * 算法原理：
 * 1. 从一个空白区域开始（所有单元格都是通路）
 * 2. 随机选择一条线（水平或垂直）将区域分成两部分
 * 3. 在这条线上随机选择一个点作为通道（保持连通性）
 * 4. 对分割后的两个子区域递归执行相同操作
 * 5. 直到子区域无法再分割
 * 
 * @author maze-demo
 */
public class DivisionGenerator implements MazeGenerator {
    private static final Logger logger = LoggerFactory.getLogger(DivisionGenerator.class);
    
    private final Random random;
    private static final int MIN_SIZE = 3; // 最小可分割区域大小

    public DivisionGenerator() {
        this.random = new Random();
    }

    public DivisionGenerator(long seed) {
        this.random = new Random(seed);
    }

    @Override
    public void generate(Maze maze) {
        logger.info("开始使用递归分割法生成 {}x{} 迷宫", maze.getRows(), maze.getCols());
        
        long startTime = System.currentTimeMillis();
        
        // 1. 初始化：所有内部单元格都是通路，边界是墙
        initializeMaze(maze);
        
        // 2. 从整个内部区域开始递归分割
        recursiveDivision(maze, 1, 1, maze.getRows() - 2, maze.getCols() - 2);
        
        // 3. 设置起点和终点
        setStartAndEnd(maze);
        
        long endTime = System.currentTimeMillis();
        logger.info("递归分割法生成完成，耗时: {}ms", endTime - startTime);
    }

    /**
     * 初始化迷宫：边界为墙，内部为通路
     */
    private void initializeMaze(Maze maze) {
        // 所有单元格初始设为通路
        for (int row = 0; row < maze.getRows(); row++) {
            for (int col = 0; col < maze.getCols(); col++) {
                maze.setCell(row, col, Cell.Type.PATH);
            }
        }
        
        // 设置边界为墙
        for (int row = 0; row < maze.getRows(); row++) {
            maze.setCell(row, 0, Cell.Type.WALL); // 左边界
            maze.setCell(row, maze.getCols() - 1, Cell.Type.WALL); // 右边界
        }
        
        for (int col = 0; col < maze.getCols(); col++) {
            maze.setCell(0, col, Cell.Type.WALL); // 上边界
            maze.setCell(maze.getRows() - 1, col, Cell.Type.WALL); // 下边界
        }
    }

    /**
     * 递归分割指定区域
     * 
     * @param maze 迷宫对象
     * @param topRow 区域上边界
     * @param leftCol 区域左边界
     * @param bottomRow 区域下边界
     * @param rightCol 区域右边界
     */
    private void recursiveDivision(Maze maze, int topRow, int leftCol, int bottomRow, int rightCol) {
        int width = rightCol - leftCol + 1;
        int height = bottomRow - topRow + 1;
        
        // 如果区域太小，停止分割
        if (width < MIN_SIZE || height < MIN_SIZE) {
            return;
        }
        
        // 决定分割方向：优先分割较长的边
        boolean horizontal;
        if (width > height) {
            horizontal = false; // 垂直分割
        } else if (height > width) {
            horizontal = true; // 水平分割
        } else {
            horizontal = random.nextBoolean(); // 随机选择
        }
        
        if (horizontal) {
            divideHorizontally(maze, topRow, leftCol, bottomRow, rightCol);
        } else {
            divideVertically(maze, topRow, leftCol, bottomRow, rightCol);
        }
    }

    /**
     * 水平分割区域
     */
    private void divideHorizontally(Maze maze, int topRow, int leftCol, int bottomRow, int rightCol) {
        // 选择分割线位置（确保分割后两个子区域都不为空）
        int minRow = topRow + 1;
        int maxRow = bottomRow - 1;
        
        if (minRow >= maxRow) {
            return; // 无法分割
        }
        
        int wallRow = minRow + random.nextInt(maxRow - minRow + 1);
        
        // 在分割线上建墙
        for (int col = leftCol; col <= rightCol; col++) {
            maze.setCell(wallRow, col, Cell.Type.WALL);
        }
        
        // 在墙上随机选择一个位置作为通道
        int passageCol = leftCol + random.nextInt(rightCol - leftCol + 1);
        maze.setCell(wallRow, passageCol, Cell.Type.PATH);
        
        logger.debug("水平分割: 在行 {} 建墙，通道在列 {}", wallRow, passageCol);
        
        // 递归分割两个子区域
        recursiveDivision(maze, topRow, leftCol, wallRow - 1, rightCol); // 上半部分
        recursiveDivision(maze, wallRow + 1, leftCol, bottomRow, rightCol); // 下半部分
    }

    /**
     * 垂直分割区域
     */
    private void divideVertically(Maze maze, int topRow, int leftCol, int bottomRow, int rightCol) {
        // 选择分割线位置
        int minCol = leftCol + 1;
        int maxCol = rightCol - 1;
        
        if (minCol >= maxCol) {
            return; // 无法分割
        }
        
        int wallCol = minCol + random.nextInt(maxCol - minCol + 1);
        
        // 在分割线上建墙
        for (int row = topRow; row <= bottomRow; row++) {
            maze.setCell(row, wallCol, Cell.Type.WALL);
        }
        
        // 在墙上随机选择一个位置作为通道
        int passageRow = topRow + random.nextInt(bottomRow - topRow + 1);
        maze.setCell(passageRow, wallCol, Cell.Type.PATH);
        
        logger.debug("垂直分割: 在列 {} 建墙，通道在行 {}", wallCol, passageRow);
        
        // 递归分割两个子区域
        recursiveDivision(maze, topRow, leftCol, bottomRow, wallCol - 1); // 左半部分
        recursiveDivision(maze, topRow, wallCol + 1, bottomRow, rightCol); // 右半部分
    }

    /**
     * 设置起点和终点
     */
    private void setStartAndEnd(Maze maze) {
        // 确保起点和终点位置是通路
        Coordinate start = new Coordinate(1, 1);
        Coordinate end = new Coordinate(maze.getRows() - 2, maze.getCols() - 2);
        
        // 强制设置这些位置为通路
        maze.setCell(start, Cell.Type.PATH);
        maze.setCell(end, Cell.Type.PATH);
        
        // 简单的连通性保证：创建一条从起点到终点的路径
        ensureConnectivity(maze, start, end);
        
        maze.setStart(start);
        maze.setEnd(end);
        
        logger.debug("设置起点: {}, 终点: {}", start, end);
    }
    
    /**
     * 确保起点和终点之间的连通性
     */
    private void ensureConnectivity(Maze maze, Coordinate start, Coordinate end) {
        // 创建一条简单的L形路径连接起点和终点
        int startRow = start.getRow();
        int startCol = start.getCol();
        int endRow = end.getRow();
        int endCol = end.getCol();
        
        // 水平路径
        int currentRow = startRow;
        int fromCol = Math.min(startCol, endCol);
        int toCol = Math.max(startCol, endCol);
        for (int col = fromCol; col <= toCol; col++) {
            maze.setCell(currentRow, col, Cell.Type.PATH);
        }
        
        // 垂直路径
        int currentCol = endCol;
        int fromRow = Math.min(startRow, endRow);
        int toRow = Math.max(startRow, endRow);
        for (int row = fromRow; row <= toRow; row++) {
            maze.setCell(row, currentCol, Cell.Type.PATH);
        }
    }

    /**
     * 随机找到一个可通行的单元格
     */
    private Coordinate findRandomPassableCell(Maze maze) {
        for (int attempt = 0; attempt < 50; attempt++) {
            int row = 1 + random.nextInt(maze.getRows() - 2);
            int col = 1 + random.nextInt(maze.getCols() - 2);
            
            if (maze.getCell(row, col).isPassable()) {
                return new Coordinate(row, col);
            }
        }
        
        // 如果随机找不到，遍历查找
        for (int row = 1; row < maze.getRows() - 1; row++) {
            for (int col = 1; col < maze.getCols() - 1; col++) {
                if (maze.getCell(row, col).isPassable()) {
                    return new Coordinate(row, col);
                }
            }
        }
        
        return new Coordinate(1, 1); // 默认位置
    }

    @Override
    public String getName() {
        return "Division";
    }
}